#include <iostream>
#include <assert.h>

using namespace std;

class List {
    struct Entry {
	Entry( int d, Entry *n, Entry *p) 
		: data( d ),
		  next( n ),
		  prev( p ) {
	    if ( prev ) {
		prev->next = this;
	    }
	    if ( next ) {
		next->prev = this;
	    }
	}
	~Entry() {
	    if ( next ) {
		next->prev = prev;
	    }
	    if ( prev ) {
		prev->next = next;
	    }
	}
		  
	int data;
	Entry *next;
	Entry *prev;
    };

    Entry *front_;
    Entry *back_;

  public:

    List() 
	    : front_( NULL ),
	      back_ ( NULL ) {
    }

    void push_front( int i ) {
	Entry *old( front_ );
	front_ = new Entry( i, front_, NULL );
	if ( NULL == old ) {
	    back_ = front_;
	}
    }

    void push_back( int i ) {
	Entry *old( back_ );
	back_ = new Entry( i, NULL, back_ );
	if ( NULL == old ) {
	    front_ = back_;
	}
    }

    int front() const {
	if ( !front_ ) throw "quit it";
	return front_->data;
    }

    int back() const {
	if ( !back_ ) throw "quit it";
	return back_->data;
    }

    void pop_front() {
	if ( !front_ ) throw "quit it";
	Entry *e = front_;
	if ( front_ == back_ ) {
	    back_ = NULL;
	}
	front_ = front_->next;
	delete e;
    }

    void pop_back() {
	if ( !back_ ) throw "quit it";
	Entry *e = back_;
	if ( front_ == back_ ) {
	    front_ = NULL;
	}
	back_ = back_->prev;
	delete e;
    }

    bool empty() const {
	if ( !front_ ) {
	    assert( !back_ );
	}
	return !front_;
    }
};

int main( int argc, char *argv[] ) {

    List l;
    l.push_front( 4 );
    l.push_front( 4 );
    l.push_front( 5 );

    assert( l.front() == 5 );
    assert( l.back() == 4 );
    cout << l.front() << endl;
    cout << l.back() << endl;

    l.push_back( 3 );
    
    assert( l.front() == 5 );
    assert( l.back() == 3 );
    cout << l.front() << endl;
    cout << l.back() << endl;

    l.pop_front();
    l.pop_back();

    assert( l.front() == 4 );
    assert( l.back() == 4 );
    cout << l.front() << endl;
    cout << l.back() << endl;

    l.pop_back();
    l.pop_back();

    assert( l.empty() );

    return 0;
}
